package com.linyaonan.leetcode.medium._LCR_038;

import java.util.LinkedList;

/**
 * 请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 *
 *
 * 示例 1:
 *
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 *
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 *
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 *
 *
 * 提示：
 *
 * 1 <= temperatures.length <= 10^5
 * 30 <= temperatures[i] <= 100
 *
 * @author: Lin
 * @date: 2024/12/12
 */
public class DailyTemperatures {

    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];

        LinkedList<Integer> stack = new LinkedList<>();
        LinkedList<Integer> stackIndex = new LinkedList<>();

        for (int i = 0; i < temperatures.length; i++) {
            int temp = temperatures[i];
            if (stack.isEmpty()) {
                stack.addLast(temp);
                stackIndex.addLast(i);
            } else {
                while (!stack.isEmpty() && temp < stack.peek()) {
                    stack.removeFirst();
                    Integer lastIndex = stackIndex.removeFirst();
                    result[i] = i - lastIndex;
                }
                result[i] = 1;
                stack.addLast(temp);
                stackIndex.addLast(i);

            }
        }

        return result;

    }

}
